package com.base.recursion;

import java.util.LinkedList;
import java.util.List;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Combine {
    /**
     *
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     *
     * 你可以按 任何顺序 返回答案。
     *
     *
     作者：liweiwei1419
     链接：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param n
     * @param k
     * @return
     */

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        // 递归跳出条件：path栈大小为k，然后将结果保存
       if (path.size()==k){
           res.add(new ArrayList<>(path));
           return;
       }
//        for (int i = begin; i <= n; i++) {
//            path.addLast(i);
//            dfs(n,k,i+1,path,res);
//            path.removeLast();
//        }
        // 遍历的上界：总数-还剩下的待组合个数+1
        for (int i = begin; i <= n-(k-path.size()+1); i++) {
            path.addLast(i);
            dfs(n,k,i+1,path,res);
            path.removeLast();
        }

    }

    public static void main(String[] args) {
        Combine combine = new Combine();
        combine.combine(4,2);

    }
}

